package cn.chen.数据结构.二叉树;

/**
 * 将数组以二叉树的前序遍历进行遍历。
 * 第n个元素的左子节点为第2*n+1个元素；
 * 第n个元素的右子节点为第2*n+2个元素；
 * 第n个元素的父节点为第(n-1)/2个元素；
 *
 */
public class ArrayBinryTree {

    private int [] tree;
    private int maxSize;

    private int index=0;

    public ArrayBinryTree(int maxSize) {
        this.maxSize = maxSize;
        tree=new int[maxSize];
    }

    public int[] getTree() {
        return tree;
    }
    //
    public void addNode(int value){

        if(tree.length>index){

            tree[index++]=value;
        }
        else {

            System.out.println("二叉树已满");
        }
    }

    // 重载前序遍历方法，少传递一个参数
    public void preOrder(int[] a){

        this.preOrder(a,0);
    }
    // 前序遍历
    /**
     *
     * @param a 要遍历的数组
     * @param root  遍历以该节点为根结点的树
     */
    private void preOrder(int[] a,int root){

        if(a.length==0)
            throw new RuntimeException("该二叉树为空");

        // 1、输出根结点
        System.out.println(a[root]);

        // 2、如果左子节点(2*root+1)不为空，就递归遍历
        int left=2*root+1;
        if(left<a.length)
            preOrder(a,left);

        // 3、如果右子节点(2*root+2)不为空，就递归遍历
        int right=2*root+2;
        if(right<a.length)
            preOrder(a,right);
    }
}
